#include <vector>
#include <cstdio>

void InsertionSort(std::vector<int>& arr) 
{
    for (int i = 1; i < arr.size(); ++i) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;
    }
}


int main() 
{
    std::vector<int> arr = { 5, 2, 8, 1, 9 };
    InsertionSort(arr);
    for (int num : arr) {
        printf("%d ", num);
    }
    return 0;
}